#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/12/9 09:19|09:19
# @Author  : yangdingyi
# @File    : 斐波那契数
# @Software: PyCharm


class Solution:
    def fib(self, N: int) -> int:
        ans_map = {}

        def work(n: int) -> int:
            if n <= 0:
                return 0
            if n == 1:
                return 1
            n_ans = ans_map.get(n, None)
            if not n_ans:
                n_ans = work(n-1) + work(n-2)
                ans_map[n] = n_ans
            return n_ans

        return work(N)


solve = Solution()

N_list = [2, 3, 4, 10, 20]
for i, n in enumerate(N_list):
    print('q[#{}]'.format(n))
    print('ans:', solve.fib(n))
